home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Snippets / Quine-McClusky 1.2 / ir.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-29  |  14.5 KB  |  579 lines  |  [TEXT/MPCC]
  1. /****************************************************************************
  2.  *
  3.  *     ir.c
  4.  *
  5.  *     By:        John A. Schlack
  6.  *     Dates:    October 1994 - November 1994
  7.  *
  8.  *     Description:
  9.  *
  10.  *        This module contains the functions that convert the prime implicants
  11.  *        to irredundant form.
  12.  *
  13.  *
  14.  *    Release Notes:
  15.  *
  16.  *        1.10    10/28/94    Created functions to reduce complete list of
  17.  *                            prime implicants to irredundant form.
  18.  *        1.20    11/29/94    Fixed bug that sometimes prevented program from
  19.  *                            obtaining irredundant form (entered loop that did
  20.  *                            not progress to solution).
  21.  *
  22.  ****************************************************************************/
  23.  
  24.  
  25. #include <stdlib.h>
  26. #include <stdio.h>
  27. #include <string.h>
  28.  
  29. #include "qmPrime.h"
  30.  
  31.  
  32. /* --------------------------------------------------------------------------------------------- */
  33.  
  34.  
  35. typedef struct funcData
  36. {
  37.     short    function;                // output decimal function
  38.     short    matchCount;                // number of prime implicants with matching decimal functions
  39.     short    matchIndex;                // index of first match
  40. } funcData;
  41.  
  42.  
  43. /* --------------------------------------------------------------------------------------------- */
  44.  
  45.  
  46. /* Prototypes */
  47.  
  48. static short    irStripUnused( irredundant * ir, funcData * function, short funcLen );
  49. static void     deleteIrredundantElem( irredundant * ir, short removeElem );
  50. static void     makeIrredundant( irredundant * ir, funcData * fd, short fdlen );
  51. static void     irSearchData( irredundant * ir, funcData * funcInfo, short fdlen );
  52. static int         searchCompare( const void * a1, const void * a2 );
  53. static short     irReduce( irredundant * ir, funcData * funcInfo, short * fdlen );
  54. static void     printIrredundant( irredundant * ir, short * function, short funcLen, short actualVars );
  55. static void     dumpIR( irredundant * ir, char * loc );
  56.  
  57.  
  58. /* --------------------------------------------------------------------------------------------- */
  59.  
  60.  
  61. /*
  62.     short irredundantForm( irredundant * ir, short * function, short funcLen,
  63.         short actualVars )
  64.  
  65.     Description:
  66.         Call this function to reduce the full list of prime implicants
  67.         to irredundant form.
  68.  
  69.     Input:
  70.         "ir" is the list of prime implicants returned from the Quine-McClusky
  71.             code in "decimal.c".  The format of this structure is already
  72.             set up for reduction.
  73.         "function" is a sorted list of decimals that define the function.
  74.         "funcLen" is the number of entries in "function".
  75.         "actualVars" is the number of variables the user chose.
  76.  
  77.     Output:
  78.         "ir" is the minimized form of prime implicants that define the function.
  79.  
  80.     Globals Modified:
  81.         none
  82.  
  83.     Returns:
  84.         1 on success and 0 on failure.
  85. */
  86.  
  87.  
  88. short irredundantForm( irredundant * ir, short * function, short funcLen,
  89.     short actualVars )
  90. {
  91.     irElement *    elem;
  92.     funcData *    funcInfo;
  93.     short        i;
  94.  
  95.     if ((funcLen <= 0) || (ir->len <= 0))
  96.         return 0;
  97.  
  98.     // make sure all elements marked as not in input
  99.     for (i=0, elem=ir->irArray; i<ir->len; i++, elem++)
  100.         elem->inOutput = 0;
  101.  
  102.     // create data storage for reduction
  103.     funcInfo = (funcData *) calloc( funcLen, sizeof( funcData ) );
  104.     if (funcInfo == NULL)
  105.         lowMemory();
  106.     for (i=0; i<funcLen; i++)
  107.         funcInfo[i].function = function[i];
  108.  
  109.     // remove prime implicants that don't have elements in output (due to don't care conditions)
  110.     if (!irStripUnused( ir, funcInfo, funcLen ))
  111.     {
  112.         printf( "\n*** ERROR!  Prime implicants do not match desired output. ***\n" );
  113.         return 0;
  114.     }
  115.  
  116.     // reduce prime implicants to irredundant form
  117.     makeIrredundant( ir, funcInfo, funcLen );
  118.  
  119.     // free memory after reduction
  120.     free( funcInfo );
  121.  
  122.     // print results
  123.     printIrredundant( ir, function, funcLen, actualVars );
  124.     return 1;
  125. }
  126.  
  127.  
  128. /* --------------------------------------------------------------------------------------------- */
  129.  
  130.  
  131. /*
  132.     static short irStripUnused( irredundant * ir, funcData * function, short funcLen )
  133.  
  134.     Description:
  135.         This function removes all prime implicants that are not present in the
  136.         current output list.  This is useful for large variable equations since
  137.         it greatly reduces the overall processing.  One will take a big performance
  138.         hit for small functions, however.
  139.  
  140.     Input:
  141.         "ir" is the list of prime implicants.
  142.         "function" is a sorted list of decimals that define the function.  This
  143.             data must be sorted into ascending decimal order.
  144.         "funcLen" is the number of entries in "function".
  145.  
  146.     Output:
  147.         "ir" is a reduced list of primes.  All those entries that do not contribute
  148.             to the current set of outputs are deleted (except those marked as in
  149.             the final output).
  150.  
  151.     Globals Modified:
  152.         none
  153.  
  154.     Returns:
  155.         Number of remaining primes implicants in the array.  If this value is
  156.         ever 0, we had an error.
  157. */
  158.  
  159.  
  160. static short irStripUnused( irredundant * ir, funcData * function, short funcLen )
  161. {
  162.     irElement *    elem;
  163.     funcData    pfunc;
  164.     size_t        size;
  165.     short        i, j, decEntries, match, oldSize;
  166.  
  167.     if (funcLen <= 0)
  168.         paramError( "irStripUnused", 3 );
  169.  
  170. #if DEBUG
  171.     dumpIR( ir, "before irStripUnused()" );
  172. #endif
  173.  
  174.     oldSize = ir->len;
  175.  
  176.     /* search each prime implicant */
  177.     elem = ir->irArray;
  178.     for (i=0; i<ir->len; i++, elem++)
  179.     {
  180.         if (elem->inOutput)
  181.             continue;
  182.  
  183.         /* check to see if it is composed of any desired output (i.e. more than just don't cares) */
  184.         match = 0;
  185.         decEntries = 1 << (elem->level - 1);
  186.         for (j=0; (j<decEntries) && (!match); j++)
  187.         {
  188.             pfunc.function = (short) elem->decimal[j];
  189.             if (bsearch( &pfunc, function, (size_t) funcLen, sizeof( funcData ),
  190.                 searchCompare ) != NULL)
  191.             {
  192.                 match = 1;
  193.                 break;
  194.             }
  195.         }
  196.  
  197.         /* remove prime implicant - only composed of don't cares */
  198.         if (!match)
  199.         {
  200.             /* free sub-element space */
  201.             if (elem->decimal != NULL)
  202.                 free( elem->decimal );
  203.             if (elem->difference != NULL)
  204.                 free( elem->difference );
  205.  
  206.             /* delete element */
  207.             deleteIrredundantElem( ir, i );
  208.             i--;            /* update loop counter */
  209.         }
  210.     }
  211.  
  212.     /* re-allocate array size to free up some space */
  213.     if (ir->len && (oldSize != ir->len))
  214.     {
  215.         size = ir->len * sizeof( irElement );
  216.         ir->irArray = realloc( ir->irArray, size );
  217.         if (ir->irArray == NULL)
  218.             lowMemory();
  219.     }
  220.  
  221. #if DEBUG
  222.     dumpIR( ir, "after irStripUnused()" );
  223.     fprintf( fp, "\n****************************************************\n" );
  224. #endif
  225.  
  226.     return (ir->len);
  227. }
  228.  
  229.  
  230. /* --------------------------------------------------------------------------------------------- */
  231.  
  232.  
  233. static void deleteIrredundantElem( irredundant * ir, short removeElem )
  234. {
  235.     irElement * elem;
  236.     size_t        size;
  237.  
  238.     elem = &(ir->irArray[removeElem]);
  239.     (ir->len)--;                            // update array size
  240.     size = (ir->len - removeElem) * sizeof( irElement );
  241.     if (size > 0)
  242.         memcpy( elem, elem + 1, size );
  243. }
  244.  
  245.  
  246. /* --------------------------------------------------------------------------------------------- */
  247.  
  248.  
  249. /*
  250.     static void makeIrredundant( irredundant * ir, funcData * fd, short fdlen )
  251.  
  252.     Description:
  253.         This function governs the actual process of reducing the primes to
  254.         a non-redundant set.  The function iterates through the primes,
  255.         searching for the best prime (one that uniquely covers the most decimal
  256.         outputs).  When one is found, that decimal is marked as part of the output.
  257.         The set of output decimals is reduced by the matches in the selected
  258.         prime.  In addition, all remaining primes that do not correspond to
  259.         remaining outputs are deleted.
  260.  
  261.     Input:
  262.         "ir" is the list of prime implicants.
  263.         "fd" is a sorted list of decimals that define the function.  This
  264.             data must be sorted into ascending decimal order.
  265.         "fdlen" is the number of entries in "function".
  266.  
  267.     Output:
  268.         "ir" is a reduced list of primes.  All those entries that do not contribute
  269.             to the current set of outputs are deleted (except those marked as in
  270.             the final output).
  271.  
  272.     Globals Modified:
  273.         none
  274.  
  275.     Returns:
  276.         none
  277. */
  278.  
  279.  
  280. static void makeIrredundant( irredundant * ir, funcData * fd, short fdlen )
  281. {
  282.     short    reduced, limitCount;
  283.  
  284.     limitCount = 0;
  285.  
  286.     // loop until all output is accounted (but be careful of infinite loops due to errors)
  287.     while( fdlen && (limitCount++ < MAX_COMBOS) )
  288.     {
  289.         // update function info from remaining prime implicants
  290.         irSearchData( ir, fd, fdlen );
  291.  
  292.         // locate required prime implicant and reduce remaining function data
  293.         reduced = irReduce( ir, fd, &fdlen );
  294.  
  295.         // we must make progress each time through the loop
  296.         if (!reduced)
  297.         {
  298.             printf( "\n*** ERROR!  Reduction failed. ***\n" );
  299.             break;
  300.         }
  301.     }
  302.  
  303.     if (limitCount >= MAX_COMBOS)
  304.         printf( "\nERROR!  Iterations did not sufficiently reduce primes.\n" );
  305. }
  306.  
  307.  
  308. /* --------------------------------------------------------------------------------------------- */
  309.  
  310.  
  311. /*
  312.     static void irSearchData( irredundant * ir, funcData * funcInfo, short fdlen )
  313.  
  314.     Description:
  315.         This function scans the primes for entries that match the remaining
  316.         output functions.  The number of matches is updated so that a "best"
  317.         prime can be selected later.
  318.  
  319.     Input:
  320.         "ir" is the list of prime implicants.
  321.         "funcInfo" is a sorted list of decimals that define the function.  This
  322.             data must be sorted into ascending decimal order.
  323.         "fdlen" is the number of entries in "function".
  324.  
  325.     Output:
  326.         "ir" and "fd" are updated with data to select a best prime.
  327.  
  328.     Globals Modified:
  329.         none
  330.  
  331.     Returns:
  332.         none
  333. */
  334.  
  335.  
  336. static void irSearchData( irredundant * ir, funcData * funcInfo, short fdlen )
  337. {
  338.     funcData *    fd, pfunc;
  339.     irElement * elem;
  340.     short        i, j, decCount;
  341.  
  342.     // zero old data
  343.     for (i=0, fd=funcInfo; i<fdlen; i++, fd++)
  344.     {
  345.         fd->matchCount = 0;
  346.         fd->matchIndex = -1;
  347.     }
  348.  
  349.     // count number of prime implicants that match each output
  350.     elem = ir->irArray;
  351.     for (i=0; i<ir->len; i++, elem++)
  352.     {
  353.         elem->uniqueCount = 0;
  354.         elem->amtInOutput = 0;
  355.  
  356.         // skip entries that are already part of final output
  357.         if (elem->inOutput)
  358.             continue;
  359.  
  360.         decCount = 1 << (elem->level - 1);
  361.         for (j=0; j<decCount; j++)
  362.         {
  363.             pfunc.function = (short) elem->decimal[j];
  364.             fd = bsearch( &pfunc, funcInfo, (size_t) fdlen, sizeof( funcData ),
  365.                 searchCompare );
  366.             if (fd != NULL)
  367.             {
  368.                 (elem->amtInOutput)++;
  369.                 (fd->matchCount)++;
  370.                 if (fd->matchIndex < 0)
  371.                     fd->matchIndex = i;
  372.             }
  373.         }
  374.     }
  375.  
  376.     // update unique count of prime implicants */
  377.     fd = funcInfo;
  378.     elem = ir->irArray;
  379.     for (i=0; i<fdlen; i++, fd++)
  380.         if (fd->matchCount == 1)
  381.             (elem[fd->matchIndex].uniqueCount)++;
  382. }
  383.  
  384.  
  385. /* --------------------------------------------------------------------------------------------- */
  386.  
  387.  
  388. static int searchCompare( const void * a1, const void * a2 )
  389. {
  390.     short    v1, v2;
  391.  
  392.     v1 = ((funcData *) a1)->function;
  393.     v2 = ((funcData *) a2)->function;
  394.     if (v1 < v2)
  395.         return -1;
  396.     if (v1 > v2)
  397.         return 1;
  398.     return 0;
  399. }
  400.  
  401.  
  402. /* --------------------------------------------------------------------------------------------- */
  403.  
  404.  
  405. /*
  406.     static short irReduce( irredundant * ir, funcData * funcInfo, short * fdlen )
  407.  
  408.     Description:
  409.         This function selects the best prime implicant, marks it as a member of
  410.         the output, and reduces the entries in the output function list and
  411.         prime implicant list.
  412.  
  413.     Input:
  414.         "ir" is the list of prime implicants.
  415.         "funcInfo" is a sorted list of decimals that define the function.  This
  416.             data must be sorted into ascending decimal order.
  417.         "fdlen" is the number of entries in "function".
  418.  
  419.     Output:
  420.         "ir" and "fd" are reduced after an output prime is selected.
  421.  
  422.     Globals Modified:
  423.         none
  424.  
  425.     Returns:
  426.         1 if process was successful or 0 on error.
  427. */
  428.  
  429.  
  430. static short irReduce( irredundant * ir, funcData * funcInfo, short * fdlen )
  431. {
  432.     unsigned char *    p;
  433.     funcData *        fd, pdata;
  434.     irElement         * elem, * olde, * newe;
  435.     size_t            size, loc;
  436.     short            i, uniqueIndex, bestIndex, count;
  437.  
  438.     elem = ir->irArray;
  439.  
  440.     // locate any unique columns and track largest set
  441.     fd = funcInfo;
  442.     uniqueIndex = bestIndex = -1;
  443.     for (i=0; i<(*fdlen); i++, fd++)
  444.     {
  445.         // we have unmatched output function - big error
  446.         if (fd->matchCount == 0)
  447.             return 0;
  448.  
  449.         // unique match
  450.         else if (fd->matchCount == 1)
  451.         {
  452.             // if first unique column found, mark it
  453.             if (uniqueIndex < 0)
  454.                 uniqueIndex = fd->matchIndex;
  455.  
  456.             // had previous unique column, take one with best output funcs
  457.             else if (uniqueIndex != fd->matchIndex)
  458.             {
  459.                 olde = &(elem[uniqueIndex]);
  460.                 newe = &(elem[fd->matchIndex]);
  461.                 if (newe->uniqueCount > olde->uniqueCount)
  462.                     uniqueIndex = fd->matchIndex;
  463.                 else if ((newe->uniqueCount == olde->uniqueCount) &&
  464.                     (newe->amtInOutput > olde->amtInOutput))
  465.                     uniqueIndex = fd->matchIndex;
  466.             }
  467.         }
  468.     }
  469.  
  470.     // always choose to process best match
  471.     if (uniqueIndex >= 0)
  472.         bestIndex = uniqueIndex;
  473.     else
  474.     {
  475.         // find prime implicant with most decimals in output
  476.         bestIndex = 0;
  477.         olde = ir->irArray;
  478.         newe = olde + 1;
  479.         for (i=1; i<(ir->len); i++, newe++)
  480.         {
  481.             if (newe->amtInOutput > olde->amtInOutput)
  482.             {
  483.                 bestIndex = i;
  484.                 olde = newe;
  485.             }
  486.         }
  487.         
  488.         // verify that we have a valid prime
  489.         if (olde->amtInOutput <= 0)
  490.             printf( "\nERROR!  Best match non-existant.\n" );
  491.     }
  492.  
  493.     // mark unique column
  494.     elem = &(ir->irArray[bestIndex]);
  495.     elem->inOutput = 1;
  496.  
  497.     // remove entries from output that are "covered" by match
  498.     count = 1 << (elem->level - 1);
  499.     p = elem->decimal;
  500.     for (i=0; i<count; i++, p++)
  501.     {
  502.         pdata.function = (short) *p;
  503.         fd = bsearch( &pdata, funcInfo, (size_t) *fdlen, sizeof( funcData ),
  504.             searchCompare );
  505.         if (fd != NULL)
  506.         {
  507.             loc = fd - funcInfo;    // pointer subtraction already reduces byte difference by element size
  508.             (*fdlen)--;
  509.             size = ((size_t) *fdlen - loc) * sizeof( funcData );
  510.             if (size > 0)
  511.                 memcpy( funcInfo + loc, funcInfo + loc + 1, size );
  512.         }
  513.     }
  514.  
  515.     // compress prime implicants
  516.     if (*fdlen > 0)
  517.         irStripUnused( ir, funcInfo, *fdlen );
  518.  
  519.     // process went normally
  520.     return 1;
  521. }
  522.  
  523.  
  524. /* --------------------------------------------------------------------------------------------- */
  525.  
  526.  
  527. static void printIrredundant( irredundant * ir, short * function, short funcLen, short actualVars )
  528. {
  529.     irElement *    elem;
  530.     short        i, cols;
  531.  
  532.     printf( "\n\n====================================================\n\n" );
  533.  
  534.     printf( "Desired Function:\n" );
  535.     for (i=0, cols=0; i<funcLen; i++, cols++)
  536.     {
  537.         if (cols >= 16)
  538.         {
  539.             putc( '\n', stdout );
  540.             cols = 0;
  541.         }
  542.         printf( "%3d ", function[i] );
  543.     }
  544.  
  545.     printf( "\n\nIrredundant Form (x%d is MSB, x0 is LSB):\n\n", actualVars - 1 );
  546.  
  547.     elem = ir->irArray;
  548.     for (i=0; i<ir->len; i++, elem++)
  549.     {
  550.         if (elem->inOutput)
  551.             printEntry( elem->decimal, elem->difference, elem->level, actualVars, NULL );
  552.     }
  553. }
  554.  
  555.  
  556. /* --------------------------------------------------------------------------------------------- */
  557.  
  558.  
  559. #if DEBUG
  560. static void dumpIR( irredundant * ir, char * loc )
  561. {
  562.     irElement *    elem;
  563.     short        i, j, count;
  564.     
  565.     fprintf( fp, "\n ---------------- Dump IR = %.40s  ----------------\n", loc );
  566.     
  567.     elem = ir->irArray;
  568.     for (i=0; i<ir->len; i++, elem++)
  569.     {
  570.         count = 1 << (elem->level - 1);
  571.         for (j=0; j<count; j++)
  572.             fprintf( fp, "%3d ", (short) (elem->decimal[j]) );
  573.         if (elem->inOutput)
  574.             fprintf( fp, "    <output>" );
  575.         fputc( '\n', fp );
  576.     }
  577. }
  578. #endif
  579.